package com.yoshino.leetcode.improve40.second;

class Solution {
    public int singleNumber(int[] nums) {
        // 三个相等的数其每个位的个数为3
        int res[] = new int[32];
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < 32; j++) {
                res[j] += (nums[i] >> j) & 1;
            }
        }
        int r = 0;
        for (int i = 0; i < 32; i++) {
            r += (res[i] % 3 << i);
        }
        return r;
    }
    public int maxProduct2(String[] words) {
        // 由于 26 个字母 < 32 位，可以用 int 表示每个 word 含有的字母是什么，作取和为 0，则两 word 无重复
        int wordInt[] = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            int temp = 0;
            for (int j = 0; j < words[i].length(); j++) {
                temp |=(1 << (words[i].charAt(j) - 'a'));
            }
            wordInt[i] = temp;
        }
        int res = 0;
        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if ((wordInt[i] & wordInt[j]) == 0) {
                    res = Math.max(res, words[i].length() * words[j].length());
                }
            }
        }
        return res;
    }
    public int maxProduct(String[] words) {
        // 由于 26 个字母 < 32 位，可以用 int 表示每个 word 含有的字母是什么，作取和为 0，则两 word 无重复
        int wordInt[] = new int[words.length];
        int res = 0;
        for (int i = 0; i < words.length; i++) {
            int temp = 0;
            for (int j = 0; j < words[i].length(); j++) {
                temp |=(1 << (words[i].charAt(j) - 'a'));
            }
            wordInt[i] = temp;
            for (int j = 0; j < i; j++) {
                if ((wordInt[i] & wordInt[j]) == 0) {
                    res = Math.max(res, words[i].length() * words[j].length());
                }
            }
        }
        return res;
    }

    public int[] twoSum(int[] numbers, int target) {
        int l = 0, r = numbers.length - 1;
        while (l < r) {
            if (numbers[l] + numbers[r] == target) {
                return new int[]{l, r};
            } else if (numbers[l] + numbers[r] > target) {
                r--;
            } else {
                l++;
            }
        }
        return new int[0];
    }
}